package LimitedTimeGame.Day_0223;

/**
 * @author zxc
 * @date 2023/02/23 09:21
 **/

import java.util.ArrayList;
import java.util.List;

/**
 * 题目 ：循环码排列
 * 题目详述 ：
 * 给你两个整数n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：
 * p[0] = start
 * p[i] 和 p[i+1]的二进制表示形式只有一位不同
 * p[0] 和 p[2^n -1]的二进制表示形式也只有一位不同
 *
 * 提示：
 * 1 <= n <= 16
 * 0 <= start < 2^n
 *
 */
public class CircularPermutation {
    /**
     * 思路 ：
     * 即，和格雷码序列一致，只不过由于第一个整数不为0，而是为[0 , 2^n]区间的取值范围之内，
     * ===》
     * 所以，从 1位格雷码序列开始遍历，直至 n位格雷码序列，都需要 与start进行 按位异或操作;
     * @param n
     * @param start
     * @return
     */
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> result = new ArrayList<>();
        // 初始化 ：即，是 0位格雷码序列;
        // 由于 0是该格雷码序列的第一个整数;
        result.add(start);
        // 从 1位格雷码序列开始获取，直至 n位格雷码序列;
        for(int i = 0 ; i < n ; i++){
            int len = result.size();
            // 为求取 n位格雷码序列的 后2^n-1个数字，
            // 需要对于 n-1位格雷码序列结果进行反序获取，同时 与1 << n 进行异或操作;
            for(int j = len - 1 ; j >= 0 ; j--){
                result.add( ((result.get(j) ^ start) | 1 << i) ^ start );
            }
        }
        return result;
    }
}
